class code5 {
    //解数独
    boolean[][] checkRow;
    boolean[][] checkCol;
    boolean[][][] checkGrid;

    public void solveSudoku(char[][] board) {
        checkRow = new boolean[9][10];// 第2行是否出现n这个数
        checkCol = new boolean[9][10];
        checkGrid = new boolean[3][3][10];// [][]这个矩阵是否出现n这个数
        // 初始化三数组
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    checkRow[i][num] = checkCol[j][num] = checkGrid[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);

    }

    public boolean dfs(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    //填数
                    for (int num = 1; num <= 9; num++) {
                        //剪枝
                        if (!checkCol[j][num] && !checkRow[i][num] && !checkGrid[i / 3][j / 3][num]) {
                            board[i][j] = (char) ('0' + num);
                            checkCol[j][num] = checkRow[i][num] = checkGrid[i / 3][j / 3][num] = true;
                            if (dfs(board)==true) return true;
                            //恢复现场
                            board[i][j] = '.';
                            checkCol[j][num] = checkRow[i][num] = checkGrid[i / 3][j / 3][num] = false;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
}